package problemLCR170;

//LCR170. 逆序对数量
//https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/

class Solution {
    public int reversePairs(int[] record) {
        return mergeSort(record, 0, record.length-1);
    }
    public int mergeSort(int[] nums, int left, int right) {
        int ret = 0;
        if(left >= right) return 0;

        int mid = left + (right-left)/2;
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid+1, right);
        int cur1 = left, cur2 = mid+1;

        int[] tmp = new int[right-left+1];
        int index = 0;
        while(cur1 <= mid && cur2 <= right) {
            if(nums[cur1] <= nums[cur2]) {
                tmp[index++] = nums[cur1++];
            }else {
                ret += mid-cur1+1;
                tmp[index++] = nums[cur2++];
            }
        }
        while(cur1 <= mid) {
            tmp[index++] = nums[cur1++];
        }
        while(cur2 <= right) {
            tmp[index++] = nums[cur2++];
        }

        for(int i = left; i<=right; i++) {
            nums[i] = tmp[i-left];
        }
        return ret;
    }
}